/***************************************************************************
 * File name: ex4.c
 *
 * Authors:  Tomer Filiba		Reuven Horon
 *           037013075			066729740
 *           sebulba@t2			sreuvenh@t2
 *
 * Exercise #: 4 (Reversi game)
 * Submission Date: 16/07/07
 **************************************************************************/

/*--------------------------------------------------------------------------
 * Include files:
 *------------------------------------------------------------------------*/
#include <stdio.h>
#include <stdlib.h>
#include <time.h>


/*--------------------------------------------------------------------------
 * constants and enums
 *------------------------------------------------------------------------*/
#define BOARD_SIZE		(8)
#define FIFTY_FIFTY		(RAND_MAX / 2)
#define SUCCESS			(0)
#define FAILURE			(1)


typedef enum
{
	TRUE = (0 == 0),
	FALSE = (0 == 1)
} bool_t;

typedef enum
{
	GM_HUMAN_HUMAN,
	GM_HUMAN_COMPUTER,
	GM_COMPUTER_HUMAN,
	GM_COMPUTER_COMPUTER
} game_mode_t;

typedef enum
{
	CELL_EMPTY = ' ',
	CELL_X = 'x',
	CELL_O = 'o'
} cell_t;


/*--------------------------------------------------------------------------
 * types and structures
 *------------------------------------------------------------------------*/
struct _game_state_t;         /* forward declaration for the next line */
typedef bool_t (*player_func_t)(struct _game_state_t * game);

typedef struct
{
	player_func_t func;       /* implementation of the player's logic */
	cell_t color;
	int score;
} player_t;

typedef struct _game_state_t
{
	player_t player_x;
	player_t player_o;
	player_t * curr_player;
	player_t * next_player;
	cell_t board[BOARD_SIZE][BOARD_SIZE];
} game_state_t;


/*=========================================================================
 *  Forward declarations:
 *========================================================================*/
bool_t game_init(game_state_t * game, game_mode_t mode);
bool_t game_main(game_state_t * game);


/*=========================================================================
 * Function implementation:
 *========================================================================*/

/*--------------------------------------------------------------------------
 * Display the menu, and wait for user to make a valid choice.
 * 
 * Parameters:
 * - mode - [OUTPARAM] This parameter will hold the choice of the user
 * 
 * Return value: TRUE if the user has made a valid choice, or FALSE if
 * the user indicated he wants to quit. 
 *
 * Notes: If the return value is FALSE, the value of 'mode' is undefined.
 *------------------------------------------------------------------------*/
bool_t main_menu(game_mode_t * mode)
{
	int choice;
	char buf[80];
	
	printf("     ===============================================\n");
	printf("     ==       Wilkommen zu das ub3r revERsi       ==\n");
	printf("     ===============================================\n\n");
	printf("Game modes:\n");
	printf("   [1] Human vs. Human\n");
	printf("   [2] Human vs. Computer\n");
	printf("   [3] Computer vs. Human\n");
	printf("   [4] Computer vs. Computer\n");
	printf("   [5] Quit\n\n");
	
	while (TRUE)
	{
		printf("Select game mode (1 - 5): ");
		if (fgets(buf, sizeof(buf), stdin) == NULL) {
			/* EOF */
			return FALSE;
		}
		if (sscanf(buf, "%d", &choice) != 1) {
			printf("Invalid input!\n");
			continue;
		}
		switch (choice)
		{
		case 1:
			*mode = GM_HUMAN_HUMAN;
			return TRUE;
		case 2:
			*mode = GM_HUMAN_COMPUTER;
			return TRUE;
		case 3:
			*mode = GM_COMPUTER_HUMAN;
			return TRUE;
		case 4:
			*mode = GM_COMPUTER_COMPUTER;
			return TRUE;
		case 5:
			return FALSE;
		default:
			printf("Invalid mode!\n");
		}
	}
}

/*--------------------------------------------------------------------------
 * The main program: create game "object", display menu, init game object,
 * start game.
 *------------------------------------------------------------------------*/
int main(int argc, const char ** argv)
{
	game_state_t game;
	game_mode_t mode;
	
	srand((unsigned int)time(NULL));
	
	if (!main_menu(&mode)) {
		printf("\nGoodbye\n");
		return FAILURE;
	}
	if (!game_init(&game, mode)) {
		printf("Error: failed to initialize game state\n");
		return FAILURE;
	}
	if (!game_main(&game)) {
		printf("Error: game reports an error (user pressed EOF)\n");
		return FAILURE;
	}
	
	system("pause");
	return SUCCESS;
}


/*=========================================================================
 * Game-logic functions
 *========================================================================*/

/*--------------------------------------------------------------------------
 * Draws the board to the console
 *
 * Parameters: 
 * - game - pointer to the game object
 *
 * Return Value: none
 *------------------------------------------------------------------------*/
void draw_board(const game_state_t * game)
{
	int i, j;
	
	system("cls");
	printf("Player %c playing:\n\n", game->curr_player->color);
	
	printf("     ");
	for (i = 0; i < BOARD_SIZE; i++) {
		printf(" %2d ", i+1);
	}
	printf("\n");
	for (i = 0; i < BOARD_SIZE; i++)
	{
		printf("     +");
		for (j = 0; j < BOARD_SIZE; j++) {
			printf("----");
		}
		printf("\b+\n");
		printf("  %2d ", i + 1);
		for (j = 0; j < BOARD_SIZE; j++) {
			printf("| %c ", game->board[i][j]);
		}
		printf("|\n");
	}
	printf("     +");
	for (j = 0; j < BOARD_SIZE; j++) {
		printf("----");
	}
	printf("\b+\n\n");
}

/*--------------------------------------------------------------------------
 * Counts the number of flips that would occur, had the player placed a 
 * stone at (row, col). If do_place is TRUE, this function will actually
 * place the stones, otherwise this function does not alter the game state.
 *
 * Parameters: 
 * - game - pointer to the game object
 * - player - pointer to the player object that attempts to place a stone
 * - row - the row where to place the stone
 * - col - the column when to place the stone
 * - do_place - a boolean indicating whether this function should actually
 *   place the stones (TRUE), or just count the number of flips (FALSE).
 *   If FALSE, this function has no side effects. If TRUE, the function
 *   updates the game board.
 *
 * Return Value: the number of flips (0 if none, which means it's an 
 * invalid move for player)
 *
 * Notes: Even when do_place is TRUE, the function does not update the 
 * players' scores.
 *------------------------------------------------------------------------*/
int simulate_flips(game_state_t * game, const player_t * player, int row, 
				   int col, bool_t do_place)
{
	int c_dirs[] = { 1,  1,  1,  0,  0, -1, -1, -1};
	int r_dirs[] = {-1,  0,  1, -1,  1, -1,  0,  1};
	bool_t possible_dirs[] = {TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE};
	int possible_dirs_left = 8;
	int rad, dir, r0, c0, r, c, i, count = 0;
	
	if (row < 1 || row > BOARD_SIZE || col < 1 || col > BOARD_SIZE) {
		return 0;
	}
	
	/* indexes are one-based */
	r0 = row - 1;
	c0 = col - 1;
	if (game->board[r0][c0] != CELL_EMPTY) {
		return 0;
	}
	
	/* look around for lines that would flip */
	for (rad = 1; possible_dirs_left > 0; rad++)
	{
		for (dir = 0; dir < 8; dir++)
		{
			if (!possible_dirs[dir]) {
				continue;
			}
			r = r0 + rad * r_dirs[dir];
			c = c0 + rad * c_dirs[dir];
			if (r < 0 || r >= BOARD_SIZE || c < 0 || c >= BOARD_SIZE || 
				game->board[r][c] == CELL_EMPTY || 
				(rad == 1 && game->board[r][c] == player->color))
			{
				/* dead end */
				possible_dirs[dir] = FALSE;
				possible_dirs_left -= 1;
				continue;
			}
			if ( rad > 1 && game->board[r][c] == player->color ) 
			{
				/* we have a line, accumulate count, mark it as 'used' */
				count += rad - 1;
				possible_dirs[dir] = FALSE;
				possible_dirs_left -= 1;
				
				/* actually place the stones */
				if (do_place) {
					r = r0;
					c = c0;
					for (i = 0; i <= rad; i++) 
					{
						game->board[r][c] = player->color;
						r += r_dirs[dir];
						c += c_dirs[dir];
					}
				}
			}
		}
	}
	
	return count;
}

/*--------------------------------------------------------------------------
 * Counts the number of flips that would result by placing a stone by 
 * 'player' at (row, col). This function has no side effects.
 *
 * Parameters: 
 * - game - pointer to the game object
 * - player - pointer to the player object that would place the stones
 * - row - the row where to place the stone
 * - col - the column where to place the stone
 *
 * Return Value: the number of flips (0 if none, which means it's an 
 * invalid move for 'player')
 *------------------------------------------------------------------------*/
int count_flips(const game_state_t * game, const player_t * player, 
				int row, int col)
{
	return simulate_flips((game_state_t*)game, (player_t*)player, 
		row, col, FALSE);
}

/*--------------------------------------------------------------------------
 * Places a stone at (row, col). The color of the stone is determined by
 * the current player. Only the current player can call this function,
 * otherwise the game state is corrupted.
 * 
 * Parameters: 
 * - game - pointer to the game object
 * - row - the row where to place the stone
 * - col - the column where to place the stone
 * 
 * Return Value: TRUE if the stone was placed successfully, FALSE if it's
 * an invalid move for current player.
 * 
 * Notes: if successful, this function will update the players' scores.
 *------------------------------------------------------------------------*/
bool_t place_stone(game_state_t * game, int row, int col)
{
	int count;
	
	/* try to place the stone, fail if it's invalid */
	count = simulate_flips(game, game->curr_player, row, col, TRUE);
	if (count == 0) {
		return FALSE;
	}
	
	/* update players' scores */
	game->curr_player->score += count + 1;
	game->next_player->score -= count;
	return TRUE;
}

/*--------------------------------------------------------------------------
 * Determines if the given player has any possible moves
 *
 * Parameters: 
 * - game - pointer to the game object
 * - player - pointer to the player object, for which we determine if there
 *   are any possible moves.
 *
 * Return Value: TRUE if there are possible moves, FALSE otherwise.
 *------------------------------------------------------------------------*/
bool_t can_play(const game_state_t * game, const player_t * player)
{
	int i, j;
	
	for (i = 1; i < BOARD_SIZE + 1; i++) {
		for (j = 1; j < BOARD_SIZE + 1; j++) {
			if (count_flips(game, player, i, j) != 0) {
				return TRUE;
			}
		}
	}
	return FALSE;
}

/*--------------------------------------------------------------------------
 * Implements a human player. Takes (row, col) from user, checks validity,
 * and performs the move.
 *
 * Parameters: 
 * - game - pointer to the game object
 *
 * Return Value: TRUE when successful, FALSE on input error (EOF)
 *
 * Notes: this function does not return until the user makes a valid move,
 * or some input error occurs. This function assumes the current player
 * has possible moves (by making sure can_play() returns TRUE before 
 * calling this function). Otherwise, this function may never return.
 *
 * Note 2: We're first using fgets to read a line, and then sscanf to
 * parse it. This is because scanf itself has all sorts of problems.
 *------------------------------------------------------------------------*/
bool_t play_human(game_state_t * game)
{
	char buf[80];
	int row, col;
	
	while (TRUE) 
	{
		printf("Enter row, col: ");
		if (fgets(buf, sizeof(buf), stdin) == NULL) {
			/* EOF */
			return FALSE;
		}
		else if (sscanf(buf, " %d , %d", &row, &col) != 2) {
			printf("Invalid format: must be 'row, col' "
				"(for example '7, 3')\n");
		}
		else if (row < 1 || row > BOARD_SIZE || col < 1 || col > BOARD_SIZE) {
			printf("Invalid range: row and col must be in 1..%d\n", 
				BOARD_SIZE);
		}
		else if (place_stone(game, row, col)) {
			/* yes, it was a valid move! */
			return TRUE;
		}
		else {
			printf("Cannot place a stone at (%d, %d), "
				"no flips would result\n", row, col);
		}
	}
}

/*--------------------------------------------------------------------------
 * Randonly (50:50 chance) chooses whether to compare using '>' or '>='.
 * This makes the computer's game less deterministic, while still choosing
 * a move that would make the maximal number of flips.
 *
 * Parameters: 
 * - a - the left-hand-side number
 * - b - the right-hand-side number
 *
 * Return Value: TRUE if (a > b) or possibly (a >= b), FALSE otherwise.
 *------------------------------------------------------------------------*/
bool_t random_gt_or_ge(int a, int b)
{
	if (rand() >= FIFTY_FIFTY) {
		return (bool_t)(a > b);
	}
	else {
		return (bool_t)(a >= b);
	}
}

/*--------------------------------------------------------------------------
 * Implements the computer player. The algorithm is simple: traverse the
 * entire board, count the number of flips that would result from placing
 * a stone at each cell, and choose the cell (row, col) that would result
 * in the maximal number of flips. We use random_gt_or_ge() to find the
 * maximal number of flips, so the game would be less deterministic.
 *
 * Parameters: 
 * - game - pointer to the game object
 *
 * Return Value: TRUE when successful, FALSE on any kind of error.
 *
 * Notes: this function assumes it has been called only if the current 
 * player has possible moves. If the computer cannot find anywhere to
 * place a stone, it's an error.
 *------------------------------------------------------------------------*/
bool_t play_computer(game_state_t * game)
{
	int i, j, f;
	int row, col;
	int max_flips = 0;
	
	for (i = 1; i < BOARD_SIZE + 1; i++) {
		for (j = 1; j < BOARD_SIZE + 1; j++) {
			f = count_flips(game, game->curr_player, i, j);
			if (random_gt_or_ge(f, max_flips)) {
				max_flips = f;
				row = i;
				col = j;
			}
		}
	}
	
	if (max_flips == 0) {
		/* nowhere to place a new stone?! this should have been detected 
		 * prior to calling us */
		return FALSE;
	}
	
	return place_stone(game, row, col);
}

/*--------------------------------------------------------------------------
 * Initializes the game object, with the given game mode
 *
 * Parameters: 
 * - game - pointer to the game object
 * - mode - the game mode (human vs human, human vs computer, etc.)
 *
 * Return Value: TRUE when successful, FALSE for invalid game mode
 *------------------------------------------------------------------------*/
bool_t game_init(game_state_t * game, game_mode_t mode)
{
	const int center = BOARD_SIZE / 2;
	int i, j;
	
	game->curr_player = &game->player_x;
	game->next_player = &game->player_o;
	game->player_x.color = CELL_X;
	game->player_o.color = CELL_O;
	game->player_x.score = 2;
	game->player_o.score = 2;
	
	/* init board */
	for (i = 0; i < BOARD_SIZE; i++) {
		for (j = 0; j < BOARD_SIZE; j++) {
			game->board[i][j] = CELL_EMPTY;
		}
	}
	game->board[center-1][center-1] = CELL_X;
	game->board[center][center] = CELL_X;
	game->board[center-1][center] = CELL_O;
	game->board[center][center-1] = CELL_O;
	
	/* init player functions (function pointers) */
	switch (mode)
	{
	case GM_HUMAN_HUMAN:
		game->player_x.func = play_human;
		game->player_o.func = play_human;
		break;
	case GM_HUMAN_COMPUTER:
		game->player_x.func = play_human;
		game->player_o.func = play_computer;
		break;
	case GM_COMPUTER_HUMAN:
		game->player_x.func = play_computer;
		game->player_o.func = play_human;
		break;
	case GM_COMPUTER_COMPUTER:
		game->player_x.func = play_computer;
		game->player_o.func = play_computer;
		break;
	default:
		return FALSE;
	}
	
	return TRUE;
}

/*--------------------------------------------------------------------------
 * Plays the game. This is the main loop, where each player plays in its
 * turn. At the end of the game, displays the players scores.
 *
 * Parameters: 
 * - game - pointer to the game object
 *
 * Return Value: TRUE when successful, FALSE for any kind of error
 *------------------------------------------------------------------------*/
bool_t game_main(game_state_t * game)
{
	int score_x, score_o;
	player_t * tmp;
	
	draw_board(game);
	
	while (TRUE)
	{
		/* make a move */
		if (!game->curr_player->func(game)) {
			return FALSE;
		}
		draw_board(game);
		
		/* if the other player can play, swap players. otherwise, skip turn */
		if (can_play(game, game->next_player)) {
			tmp = game->curr_player;
			game->curr_player = game->next_player;
			game->next_player = tmp;
		}
		else if (!can_play(game, game->curr_player)) {
			/* both players have no possible moves -- end of game */
			break;
		}
	}
	
	/* display scores */
	score_x = game->player_x.score;
	score_o = game->player_o.score;
	printf("\n\nGame has ended. The scores are:\n");
	printf("Player X: %d\nPlayer O: %d\n", score_x, score_o);
	if (score_x > score_o) {
		printf("Player X wins!\n");
	}
	else if (score_o > score_x) {
		printf("Player O wins!\n");
	}
	else {
		printf("Tike!\n");
	}
	
	return TRUE;
}

/**************************************************************************
                               End of file
***************************************************************************/